1. Field of the Invention
The present invention relates to an apparatus for retrieving data which had been stored with hashing process, and specifically relates to a data retrieving apparatus used for a data-driven processor which generates a pair of data wherein identification data match with each other and performs "fire" processing.
2. Description of Related Art
FIG. 1 is a conceptual view of processing of a data-driven processor, which shows an aspect of addition of two data. In FIG. 1, when a packet 81 having a value "A" and an annexed identifier "a" is given to a matching memory 87, an identifier field comparator 84 retrieves whether or not a packet having an identifier matching with the identifier "a" of the packet 81 is stored in a waiting memory 85. In FIG. 1, a packet 82 having a value "B" and the identifier "a" is stored, and therefore this packet 82 is read out from the waiting memory 85 and is sent to a data pair forming unit 86 together with the inputted packet 81.
The data pair forming packet 86 combines the packet 81 and the packet 82, and forms data 83 wherein the identifier "a" is added to the value "A" and the value "B" (this is referred to as fire), and arithmetic operation is executed in a data processing unit 88.
In an example in FIG. 1, the packet 82 having the same identifier "a" as that of the packet 81 inputted to the waiting memory 85 is kept stored, but when a packet having the same identifier as that of the packet 81 inputted to the waiting memory 85 is not stored, the inputted packet 81 is stored in the waiting memory 85, and is made to wait until a packet having the identifier matching with this is inputted.
Thus the matching memory has a role of retrieving a packet to be operated in the data-driven processor.
In the normal data-driven processor, the bit width of identifier is several dozens of bits, and therefore if addresses of memory are assigned for each identifier, the memory capacity becomes enormous. Therefore, conventionally a memory, wherein the bit width is compressed (hereinafter referred to as hash) as a memory used for the matching memory, is used as a memory address (hereinafter referred to as hash memory).
FIG. 2 is a bit map showing a configuration of one example of an inputted packet, and FIG. 3 is a block diagram showing a configuration of one example of a hash memory.
An inputted packet comprises a 18-bit operand data OD to be operated, a seven-bit operation code OC which is a code showing the content of operation, a one-bit processor select bit PS, a one-bit FC processing select bit showing whether the inputted packet is a two-input instruction or a one-input instruction, and a left/right data select bit showing arrangement to left or right responding to the sequence of operation, and is constituted with a total of 62 bits further comprising a selection code SC performing various selections, a nine-bit color/generation identification number DN showing the attribute such as input sequence of the inputted data and 21-bit node number NN showing a location where operation is to be performed. Then, a 31-bit identifier which is an identification code is constituted with the processor select bit PS, the color/generation identification number DN and the node number NN.
A hash memory 601 is such that a total of nine bits consisting of lowest three bits of the color/generation identification number DN and lowest six bits of the node number NN are accessed as a hashed address, and a read/write signal W/R.multidot.H determining a read/write cycle and a set/reset signal S/R renewing write-in data and a presence bit PB showing "valid" or "invalid" of each address are given thereto.
The write-in data to be stored consists of a total of 40 bits of 18 bits of operand data, 21 bits of identifier (6 bits of color/generation number DN and 15 bits of node number NN) and one bit of processor select bit PS. Also, in the hash memory 601, the one-bit presence bit PB is stored additionally, and one word consists of a total of 41 bits. Also, an address space is 2.sup.9 =512, and the hash memory 601 has a capacity of 41 bits/word .times.512.
Where the hash memory is used, a crash at the same address, so-called hashed address conflict might occur when the hashed address (hereinafter referred to as hashed address) is accessed.
In other words, the hashed address conflict is caused because, even if a part of the identifier is set as a hashed address and the hashed address matches with data already stored in the hash memory, when the data whose remaining identifier does not match is accessed, the address for storing that data has been already occupied.
As a prior art for avoiding this hashed address conflict, the data-driven processor disclosed on P.19-P.26 in "Report of research and development in Oki Electric Co., Ltd." and the invention (U.S. Pat. No. 5,072,377, issued on Dec. 10, 1991 ) by the present applicant are publicly known. See U.S. Pat. No. 5,072,377 filed Nov. 17, 1987.
The former installs a chain field showing correlation of addresses in the hash memory, and retrieves data to become a pair by sequentially referring the addresses shown in the chain field in the hash memory if a hashed address conflict occurs.
The latter installs a tag comparator comparing the value of identifier, and when a hashed address conflict occurs, compares the value of the identifier of the inputted data with that of the identifier of the read out data, and stores the data having a smaller-value identifier in the hash memory, and the data having a larger-value identifier is added a through flag, and is circulated in the apparatus without being processed until it can be stored in the hash memory, finally being inputted to the hash memory. This value of the identifier is determined according to the processing sequence of a program, and therefore value comparison of the identifiers is performed and the data having the identifier of smaller value is stored in the hash memory, and thereby a generation of an infinite loop caused by a dependent relation of data in executing the program is prevented.
However, the former sequentially retrieves data to become a pair by tracing the addresses specified by the chain field when a hashed address conflict occurs, and therefore there is a problem that, when frequency of occurrence of hashed address conflict increases, the processing time per data is extended, and the processing efficiency of the whole processor is remarkably reduced.
Accordingly, the capacity of the hash memory is required to be increased to reduce the frequency of occurrence of hashed address conflict, and the use of the hash memory for reducing the memory capacity becomes meaningless.
Also, the latter compares the value of the identifier of data, and replaces data in the hash memory, and therefore the mechanism becomes complicated. Also, data wherein the through flag is set circulates in the processor, and occupies the processor during that time, and therefore the processing efficiency of the processor is reduced.
On the other hand, the hashed address, as described above, for example, is generated by connecting three bits from nine-bit color/generation identification number DN and six bits from 21-bit node number NN of the identifier. And the address space of the hash memory of 2.sup.9 is divided into color/generation sections of 2.sup.3 (=8), and one color/generation section has 2.sup.6 (=64) address spaces. Accordingly, when the lowest three bits of the color/generation identification number DN of the inputted data are equal, they access to the same color/generation section, and when the color/generation sections are small in number, the frequency of access to the address spaces of one section (=2.sup.6) increases, resulting in an increase in frequency of hashed address conflict. This means that, if the lowest three bits of the color/generation identification number DN of the inputted data are equal, despite that it has as many as 2.sup.9 (=512) address spaces, virtually a eighth (=64) of 2.sup.9 spaces thereof are accessed. Therefore, the frequency of hashed address conflict sometimes increases by eight times.